import { IQueue } from "./types";
import ArrayList from '@/sources/ArrayList'
import { IIterator } from "../types";

// 双端队列
export default class Queue<T = number> implements IQueue<T> {
    private al: ArrayList<T>
    private frontIndex = 0;
    constructor() {
        // 初始化arrayList
        this.al = new ArrayList<T>()
    }

    /**
     * 获取队列的长度
     */
    size() {
        return this.al.size()
    }

    /**
     * 判断队列是否为空
     */
    isEmpty() {
        return this.al.isEmpty();
    }

    /**
     * 清空队列元素
     */
    clear() {
        this.al.clear()
    }

    /**
     * 获取index
     * @param index 
     */
    private getIndex(index: number) {
        return (this.frontIndex + index) % this.al.arr.length || 0;
    }

    /**
     * 入队, 默认从尾部
     * @param element 
     */
    enQueue(element: T) {
        // 确保数组的容量
        this.ensureCapicity();
        const i = this.getIndex(this.size())
        this.al.array[i] = element;
        this.al.sizes++;
    }



    /**
     * 出队
     */
    deQueue() {
        const frontIndex = this.frontIndex
        // 保存老的值
        const oldVal = this.al.get(frontIndex);
        this.al.array[frontIndex] = undefined;

        // frontIndex, 前进1
        this.frontIndex = this.getIndex(1);
        // 返回新的值
        this.al.sizes--;
        return oldVal
    }



    /**
     * 获取队头元素
     */
    front() {
        return this.al.get(this.frontIndex)
    }

    /**
     * 遍历队列
     */
    forEach(cb: IIterator<T>) {
        this.al.forEach((ele, i) => {
            cb(ele, i)
        })
    }

    /**
     * 确保数组的容量
     */
    private ensureCapicity() {
        // 检查数组是否需要扩容
        if (this.al.sizes >= this.al.arr.length) {
            this.enlargeCapicity();
        }
    }

    /**
     * 扩容
     */
    private enlargeCapicity() {
        // 扩容两倍
        const newCapicity = this.al.DEFAULT_CAPICITY << 1;
        // 创建新数组
        const newArr = new Array<T>(newCapicity)

        // 将老的数组移动到新的数组中
        const oldArr = this.al.arr,
            sizes = this.al.sizes;
        let i = 0;
        for (; i < sizes; i++) {
            // 获取原来对应的下标
            newArr[i] = oldArr[this.getIndex(i)]!
        }

        // 更新数组
        this.al.arr = newArr;

        // 重置frontIndex
        this.frontIndex = 0
    }

} 